/*
程序设计题: 单链表实验
1.	从键盘输入若干大于0的整数，用这些整数构造一个单链表.当用户输入小于等于0的值时，创建链表结束并在终端打印输出这个链表。
2.	在链表中查找某结点，如果能找到输出这个结点是第几个结点，如果找不到，输出:找不到此结点。
3.	删除指定结点: 如果指定的被删除结点存在就删除它,然后打印：已经删除，如果不存在，输出信息：链表中没有此结点，无法删除。
4.	删除重复结点：如果链表中有重复的元素，删除重复的元素，使得所有值最多只出现一次，例如，如果链表中有3个结点的值是100，那么需要删除两个值为100的结点。
 只保留一个值为100的结点。删除重复结点后打印输出整个链表
 */

#include<iostream>
#include<string>
using namespace std;
typedef int DataType;

class Node
{
    friend class LinkList;
private:
    DataType data;
    Node *next;
public:
    Node(Node *ptr=NULL)
    { next=ptr;}
    Node(int item,Node *ptr=NULL)
    {
        data=item;
        next=ptr;
    }
};

class LinkList{
//链表类
private:
    Node* head;
    Node* tail;
    //链表的表头指针、尾指针
public:
    LinkList()
    {
        head=new Node();//表头结点
        head->next=NULL;
        tail=head;
    }
    ~LinkList();
    void PrintList();//打印输出单链表
    void CreateListF();//头插法创建链表
    int SearchIndex(DataType data);
    void SearchData();
    bool Delete(DataType data);
    void DeleteNode();
    void Distinct();
    bool IsBeforeHasNode(DataType  data, int index);
};

bool LinkList:: IsBeforeHasNode(DataType data, int index) {
    if (index < 1) return false;

    Node *p = head->next;
    if (p == NULL) return false;

    int k = 0;
    while (p != NULL) {
        if (p->data == data) {
            return true;
        }
        p = p->next;
        k++;
        if (k == index) return false;
    }
    return false;
}

void LinkList::Distinct() {
    Node *p = head->next;
    Node *beforeNode;
    if (p == NULL) return;

    int k = 0;
    while (p != NULL) {
        if (k > 0 && this->IsBeforeHasNode(p->data, k)) {
            beforeNode->next = p->next;
            delete p;

            if (beforeNode->next == NULL)tail = beforeNode;

            p = beforeNode->next;
        }
        else {
            beforeNode = p;
            p = p->next;
            k++;
        }
    }
}

int LinkList::SearchIndex(DataType data) {
    Node *p = head->next;
    if (p == NULL) return -1;
    int index = -1;
    int k = 0;
    do {
        if (p->data == data) {
            index = k;
            break;
        }
        p = p->next;
        k++;
    } while (p != NULL);
    return index;
}

bool LinkList::Delete(DataType data) {
    Node *p = head;

    while (p != NULL) {
        if (p->next != NULL && p->next->data == data) break;
        p = p->next;
    }

    if (p == NULL) return false;

    Node *q = p->next;
    p->next = q->next;
    delete q;

    if (p->next == NULL)tail = p;

    return true;
}

LinkList::~LinkList() {
    Node *p;
    p = head;
    while (p != NULL) {
        p = p->next;//p指向下一个结点
        delete head;//删除head所指向的结点
        head = p;//head更新，指向下一个即将被删除结点
    }
}

//1.	从键盘输入若干大于0的整数，用这些整数构造一个单链表.当用户输入小于等于0的值时，创建链表结束并在终端打印输出这个链表。
void LinkList::CreateListF()//头插法创建链表
{
    DataType data;
    cout << "请输入数据(输入小于或等于0的值结束):" << endl;
    cin >> data;
    Node *s;
    while (data > 0) {
        s = new Node(data, head->next);
        head->next = s;
        cout << "请输入数据(输入小于或等于0的值结束):" << endl;
        cin >> data;
    }
}

void LinkList::PrintList() {
    Node *p = head->next;
    while (p->next != NULL) {
        cout << p->data << "-->";
        p = p->next;
    }
    if (p != NULL)cout << p->data;
    cout << endl;
}

//在链表中查找某结点，如果能找到输出这个结点是第几个结点，如果找不到，输出:找不到此结点。
void LinkList:: SearchData() {
    DataType data;
    cout<<"请输入查找结点数据(输入小于或等于0的值结束):"<<endl;
    cin>>data;

    while(data>0)
    {
        int index = this->SearchIndex(data);
        if (index == -1) cout << "找不到此结点" << endl;
        else cout << "这个结点是第" << (index + 1) << "结点" << endl;
        cout<<"请输入查找结点数据(输入小于或等于0的值结束):"<<endl;
        cin>>data;
    }
}

//3.删除指定结点: 如果指定的被删除结点存在就删除它,然后打印：已经删除，如果不存在，输出信息：链表中没有此结点，无法删除。
void LinkList:: DeleteNode() {
    DataType data;
    cout<<"请输入查找删除结点数据(输入小于或等于0的值结束):"<<endl;
    cin>>data;

    while (data > 0) {
        if (this->Delete(data)) {
            cout << "已经删除" << endl;
        } else cout << "链表中没有此结点，无法删除。" << endl;
        cout<<"请输入查找删除结点数据(输入小于或等于0的值结束):"<<endl;
        cin >> data;
    }
}

int main() {
    cout << "单链表实验" << endl;

    //1.从键盘输入若干大于0的整数，用这些整数构造一个单链表.当用户输入小于等于0的值时，创建链表结束并在终端打印输出这个链表。
    cout << "1.从键盘输入若干大于0的整数，用这些整数构造一个单链表.当用户输入小于等于0的值时，创建链表结束并在终端打印输出这个链表。" << endl;
    LinkList list;
    list.CreateListF();
    list.PrintList();

    //2.在链表中查找某结点，如果能找到输出这个结点是第几个结点，如果找不到，输出:找不到此结点。
    cout << "2.在链表中查找某结点，如果能找到输出这个结点是第几个结点，如果找不到，输出:找不到此结点。" << endl;
    list.SearchData();

    //3.删除指定结点: 如果指定的被删除结点存在就删除它,然后打印：已经删除，如果不存在，输出信息：链表中没有此结点，无法删除。
    cout << "3.删除指定结点: 如果指定的被删除结点存在就删除它,然后打印：已经删除，如果不存在，输出信息：链表中没有此结点，无法删除。" << endl;
    list.DeleteNode();

    //4.删除重复结点：如果链表中有重复的元素，删除重复的元素，使得所有值最多只出现一次，例如，如果链表中有3个结点的值是100，那么需要删除两个值为100的结点。
    //只保留一个值为100的结点。删除重复结点后打印输出整个链表
    cout << "4.删除重复结点：如果链表中有重复的元素，删除重复的元素，使得所有值最多只出现一次，例如，如果链表中有3个结点的值是100，那么需要删除两个值为100的结点。只保留一个值为100的结点。删除重复结点后打印输出整个链表" << endl;
    list.Distinct();
    list.PrintList();

    return 0;
}